package com.wfm.leetcode.editor.cn;

/**
 * 动态规划
 * left[i]数组代表：在位置i，右往左看，最高的柱子有多高。然后求解的时候是从左到右遍历才求得出动态数组
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */

public class PFour2接雨水{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 动态规划
    public int trap(int[] height) {
        int ans = 0;
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        for (int i = height.length-2; i >=0; i--) {
            right[i]=Math.max(right[i+1],height[i+1]);
        }
        for (int i = 1; i <height.length; i++) {
            left[i]=Math.max(left[i-1],height[i-1]);
        }
        for (int i = 0; i < height.length; i++) {
            int t = Math.min(left[i],right[i]);
            if(t>height[i]){
                ans+=t-height[i];
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFour2接雨水().new Solution();
    }
}